1. Field of the Invention
This invention is related to digital systems and, more particularly, to caches within digital systems.
2. Description of the Related Art
Processors and/or the computer systems including the processors typically provide caches to alleviate the high memory latency frequently experienced in computer systems. Generally, a cache is a relatively small, high speed memory which may store copies of data corresponding to various recently-accessed memory locations. Generally, cache storage is allocated and deallocated in units of cache lines (a group of bytes from contiguous memory locations). In other words, the cache may include multiple entries, and each entry may include storage for a cache line of bytes. If requested data for an access is not in the cache (a “miss”), an entry is allocated for the cache line including the requested data and the cache line is filled into the allocated entry. Subsequently, the data may be found in the cache upon request (a “hit”). In some cases, a portion of the cache line (often called a “sector”) may be valid while other portions are invalid. However, the entire cache entry is allocated for the cache line if one or more of the sectors are valid.
Since a cache is generally smaller than the system memory for which the cache is used, cache lines currently stored in the cache may need to be deleted from the cache (referred to as “evicting” the cache line) to make room for newly accessed data which is not stored in the cache. The newly accessed data may be statistically more likely to be accessed again in the near future than is data that has been in the cache for some time, particularly for code which exhibits locality of reference (in which access to a particular datum makes access to nearby data within the memory more likely). Typically, the cache selects one or more cache entries which are eligible to store data corresponding to a given transaction, and searches these entries to detect a hit or miss. In a direct-mapped cache, one entry is eligible to store the data based on the address of the data. If a miss is detected in a direct mapped cache, that cache line in that entry is evicted. In a set associative cache, on the other hand, two or more entries are eligible to store the data based on the address of the data. The cache line of any one of the two or more entries could be evicted on a miss. Set associative caches employ a replacement policy to select one of the two or more eligible entries for eviction. A variety of replacement policies exist.
Unfortunately, it is frequently difficult to predict, from a viewpoint external to the cache, which cache entry will be allocated to a given cache line. Complex monitoring of the transactions presented to the cache, along with detailed knowledge of the implemented replacement policy, would be required to determine the state of the replacement policy at any given point in time. During the typical access of various data from memory, this lack of ability to determine which cache entry will be selected is generally not a problem. However, in some cases, it may be desirable or even critical to know which cache entry will be allocated according to the replacement policy. For example, in certain testing situations, it may be desirable to ensure that a particular entry is used for a particular transaction. Additionally, knowing which entry will be allocated to a cache miss could be used to intentionally evict the cache line in the entry (e.g. to flush the particular entry from the cache). Thus, a method for easily determining which entry will be selected by a replacement policy is desired.